Năm 639, vị khalip thứ nhì của quốc gia Hồi giáo là Umar phái tướng Amr ibn al-As với khoảng 4.000 quân đánh Ai Cập. Năm 640, đoàn quân này được thêm 5.000 quân tiếp viện và đánh bại quân Đông La Mã (Byzantine) ở trận Heliopolis. Sau khi chiếm được đồn Babylon (Babylon của Cairo, phân biệt với Babylon ở Iraq) ở châu thổ sông Nil (ngày 9 tháng 4 năm 641), ông lập trại quân Fostat năm 643 bên cạnh đồn này để kiểm soát các vùng đất đã chiếm được. Fostat là khởi điểm của thủ đô Cairo sau này.

Amr chuyển quân đánh Alexandria, và lấy được thành phố này khi một hoà ước được ký kết ngày 8 tháng 11 năm 641.

Alexandria bị Đông La Mã tái chiếm năm 645 nhưng bị Amr lấy lại năm 646. Năm 654 hoàng đế Đông La Mã Constans II phái hạm đội đi tái chiếm Ai Cập nhưng hạm đội này bị thua trận. Từ đó Đông La Mã không làm được cố gắng lớn nào để tái chiếm xứ này.

* Các thống đốc Ả rập ở Ai Cập (641 - 969):

1. Amr ibn al-As: 640-646
2. Abdallah ibn Sa'ad: 646-656
3. Muhammad ibn Abi Hudhayfa: 656-657
4. Qays ibn Sa'ad: 657
5. Malik ibn al-Harith: 657
6. Muhammad ibn Abi Bakr: 657-658
7. Amr ibn al-'As: 658-664
8. Utba ibn Abi Sufyan: 664-665
9. Utba ibn Amir: 665-667
10. Maslama ibn al-Ansari Mukhallad: 667-682
11. Sa'id ibn Yazid ibn al-Qama al-Azdi: 682-684
12. Abd al-Rahman al-ibn Utba Fihri: 684
13. Abd al-Aziz ibn Marwan ibn al-Hakam: 685-705
14. Abdallah ibn Abd al-Malik ibn Marwan ibn al-Hakam: 705-709
15. Qurra ibn al-Sharik Absi: 709-715
16. Abd al-Malik ibn al-Rifa'a Fahmi: 715-717
17. Ayyub ibn Sharhabil: 717-720
18. Bishr ibn al-Safwan Kalbi: 720-721
19. Handhala ibn al-Safwan Kalbi: 721-724
20. Muhammad ibn Abd al-Malik ibn Marwan: 724
21. Al-Hurr ibn Yusuf: 724-727
22. Abd al-Malik ibn al-Rifa'a Fahmi: 727
23. Al-Walid ibn Rifa'a ibn Thabit al-Fahmi: 727-735